package com.yiwenup.sorting._04_insertion;

import com.yiwenup.sorting.base.Sort;

/**
 * 插入排序
 * 时间复杂度：最好 - O(n)；最坏 - O(n²)；平均复杂度 - O(n²)【跟逆序对的数量成正比】
 * 空间复杂度：O(1)
 * 稳定性：稳定
 * <p>
 * 之前的【交换】修改为【挪动】
 **/
public class InsertionSortV2<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void work() {
        for (int begin = 1; begin < array.length; begin++) {
            int cur = begin;
            E e = array[cur];
            while (cur > 0 && cmp(e, array[cur - 1]) < 0) {
                array[cur] = array[cur - 1];
                cur--;
            }
            array[cur] = e;
        }
    }
}
